package PAT;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

public class PAT1153 {
    private static int index =0 ;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        Map<String,Integer> map = new HashMap<>();
        while (n-- > 0) {
            map.put(scanner.next(),scanner.nextInt());
        }
        scanner.nextLine();
        for (int i = 0; i < m; i++) {
            if(i!=0) System.out.println("");
            String s = scanner.nextLine();
            String[] ss = s.split(" ");
            switch (ss[0]){
                case "1":{
                    deal1(map,ss[1]);
                    break;
                }
                case "2":{
                    deal2(map,ss[1]);
                    break;
                }
                default:{
                    deal3(map,ss[1]);
                }
            }
        }
    }



    private static void deal3(Map<String, Integer> map, String s) {
        System.out.printf("Case %d: 3 %s",++index,s);
        HashMap<String, Integer> tMap = new HashMap<>();
        AtomicInteger temp = new AtomicInteger();
        map.entrySet().stream().filter(k->k.getKey().contains(s)).forEach(k->{
            String s1 = k.getKey().split(s)[0].substring(1);
            tMap.merge(s1,1,Math::addExact);
            temp.getAndIncrement();
        });
        if(temp.get()==0) {
            System.out.print("\nNA");
            return;
        }
        ArrayList<Map.Entry<String, Integer>> entries = new ArrayList<>(tMap.entrySet());
        entries.sort(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return o2.getValue().equals(o1.getValue())? o1.getKey().compareTo(o2.getKey()) : o2.getValue()- o1.getValue();
            }
        });
        for (Map.Entry<String, Integer> entry : entries) {
            System.out.printf("\n%s %d",entry.getKey(),entry.getValue());
        }
    }

    private static void deal2(Map<String, Integer> map, String s) {
        System.out.printf("Case %d: 2 %s",++index,s);
        int ans  =0;
        int num =0;
        AtomicInteger temp = new AtomicInteger();
        for (Map.Entry<String, Integer> stringIntegerEntry : map.entrySet().stream().filter(k -> k.getKey().contains(s)).collect(Collectors.toSet())) {
            ans += stringIntegerEntry.getValue();
            temp.getAndIncrement();
            num++;
        }
        if(temp.get()==0) {
            System.out.print("\nNA");
            return;
        }
        System.out.printf("\n%d %d",num,ans);
    }

    private static void deal1(Map<String, Integer> map, String s) {
        System.out.printf("Case %d: 1 %s",++index,s);
        AtomicInteger temp = new AtomicInteger();
        map.entrySet().stream().filter(k->k.getKey().contains(s)).sorted(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return o2.getValue()-o1.getValue();
            }
        }).forEach(k->{
            temp.getAndIncrement();
            System.out.printf("\n%s %d",k.getKey(),k.getValue());
        });
        if(temp.get()==0){
            System.out.print("\nNA");
        }
    }
}